## Este codigo partiu de {{{ http://code.activestate.com/recipes/199121/ (r1)
# mas sofreu grandes para sincronismo com o resto da aplicacao.
#
# genetic.py
#



import random, threading

MAXIMIZE, MINIMIZE = 11, 22


    
class Individual(object):
    alleles = (0,1)
    length = 30
    seperator = ''
    optimization = MINIMIZE

    def __init__(self, chromosome=None):
        self.chromosome = chromosome or self._makechromosome()
        self.score = None  # set during evaluation
    
    def _makechromosome(self):
        "makes a chromosome from randomly selected alleles."
        return [random.choice(self.alleles) for gene in range(self.length)]

    def evaluate(self, optimum=None):
        "this method MUST be overridden to evaluate individual fitness score."
        pass
    
    def crossover(self, other):
        "override this method to use your preferred crossover method."
        return self._twopoint(other)
    
    #~ def mutate(self, gene):
        #~ "override this method to use your preferred mutation method."
        #~ self._pick(gene) 
    
    # sample mutation method
    def _pick(self, gene):
        "chooses a random allele to replace this gene's allele."
        self.chromosome[gene] = random.choice(self.alleles)
    
    # sample crossover method
    def _twopoint(self, other):
        "creates offspring via two-point crossover between mates."
        left, right = self._pickpivots()
        def mate(p0, p1):
            chromosome = p0.chromosome[:]
            chromosome[left:right] = p1.chromosome[left:right]
            import copy
            child = p0.__class__(chromosome)
            child._repair(p0, p1)
            child = child.copy()
            child.score = None
            return child
        return mate(self, other), mate(other, self)

    # some crossover helpers ...
    def _repair(self, parent1, parent2):
        "override this method, if necessary, to fix duplicated genes."
        pass

    def _pickpivots(self):
        left = random.randrange(1, self.length-2)
        right = random.randrange(left, self.length-1)
        return left, right

    #
    # other methods
    #

    def __repr__(self):
        "returns string representation of self"
        return 'chromosome="%s" score=%s' % \
               (self.seperator.join(map(str,self.chromosome)), self.score)

    def __cmp__(self, other):
        if self.optimization == MINIMIZE:
            return cmp(self.score, other.score)
        else: # MAXIMIZE
            return cmp(other.score, self.score)
    
    def copy(self):
        import copy
        son = copy.deepcopy(self)
        
        return son


class Environment(threading.Thread):
    individual2Evaluate = None
    
    def __init__(self, kind, population=None, size=100, maxgenerations=100, 
                 crossover_rate=0.90, mutation_rate=0.01, optimum=None, numSort=None,lastWinner=None):
        threading.Thread.__init__(self)
        
        self.kind = kind
        self.size = size
        self.optimum = optimum
        self.numSort=numSort
        self.population = population or self._makepopulation(lastWinner)
        if lastWinner is not None:
            self.population[0]=lastWinner
        
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate
        self.maxgenerations = maxgenerations
        self.generation = 0
        
        self.eventEvaluationWant=threading.Event()
        self.eventEvaluationNeed=threading.Event()
        
        for indiv in self.population:
            indiv.everyone+=self.size
        
    def _makepopulation(self,lastWinner = None):
        "1, 2, 3, 4, 5, 6, 7", "0011 0011 1001 1001 1001 1011 0101"
        
        if lastWinner:
            everyone=lastWinner.everyone
        else:
            everyone=0
            
        if self.numSort==None:
            pop = [self.kind(everyone=everyone) for individual in range(self.size)]
        else:
            pop =  [self.kind(numSort=self.numSort,everyone=everyone) for individual in range(self.size)]
            
        from copy import deepcopy
        if lastWinner:
            for indi in pop:
                indi.chromosome[0]=deepcopy(lastWinner.chromosome[0])
                
        return pop
    
    def run(self):
        for individual in self.population:
            self.evaluateIndiv(individual)
            #individual.evaluate(self.optimum)
            
        self.population.sort()
        self.report()
        
        while not self._goal():
            self.step()
            
        self.individual2Evaluate = 'end'
        self.eventEvaluationWant.set()
        
    
    def evaluateIndiv(self,individual):
        if individual.score is not None:
            return
        self.individual2Evaluate=individual
        
        #print "genetic waiting robot evaluation"
        self.eventEvaluationWant.set()
        
        self.eventEvaluationNeed.clear()
        self.eventEvaluationNeed.wait()
        #print "genetic received robot evaluation"
        #evaluationDone
        self.individual2Evaluate = None
        
        
    def _goal(self):
        #print "Goal: bestscore",self.best.score
        return self.generation +1 >= self.maxgenerations or \
               self.best.score == self.optimum
        
    
    def step(self):
        
        self._crossover()
        self.generation += 1
        self.population.sort()
        self.report()
    
    def _crossover(self):
        everyone = self.best.everyone
        
        for indiv in self.population:
            indiv.everyone=everyone+self.size
        
        next_population = [self.best.copy()]
        count_individual_blocked=0
        
        
        
        while len(next_population) < self.size:
            mate1 = self._select()
            if random.random() < self.crossover_rate:
                mate2 = self._select()
                offspring = [mate1.crossover(mate2)]
            else:
                offspring = [mate1]
            for individual in offspring:
                individual=individual.copy()
                individual.score=None
                self._mutate(individual)
                
                
                if individual not in next_population or count_individual_blocked>5:
                    self.evaluateIndiv(individual)
                    next_population.append(individual)
                    count_individual_blocked=0
                else:
                    count_individual_blocked+=1
        self.population = next_population[:self.size]

    def _select(self):
        "override this to use your preferred selection method"
        return self._tournament()
    
    def _mutate(self, individual):
        #~ print "indiv era:", individual.chromosome
        for gene in individual.chromosome:
            import geneticRoom
            if isinstance(gene,geneticRoom.SortGene):
                gene.mutate()
            elif random.random() < self.mutation_rate:
                gene.mutate()
            
        #~ print "indiv ficou:", individual.chromosome

    #
    # sample selection method
    #
    def _tournament(self, size=8, choosebest=0.90):
        competitors = [random.choice(self.population) for i in range(size)]
        competitors.sort()
        if random.random() < choosebest:
            return competitors[0]
        else:
            return random.choice(competitors[1:])
    
    def best():
        doc = "individual with best fitness score in population."
        def fget(self):
            return self.population[0]
        return locals()
    best = property(**best())

    def report(self):
        print "="*70
        print "generation: ", self.generation, "total people =",self.best.everyone
        for indiv in self.population:
            print indiv




